旅游交友的网站建设,引擎搜索,制作网站网页设计,福建银瑞建设工程有限公司网站文章目录前言1.大体思路2.具体代码实现1.类模板的创建2.构造函数1.无参构造2.拷贝构造 迭代器构造和给定n个val值构造以及析构函数3.空间扩容1.reserve2.resize4.操作符重载1.[ ]重载2.赋值运算符重载5.数据增加和删除1.尾插2.任意位置插入3.任意位置删除4.尾删6.一些其他接口3…
文章目录前言1.大体思路2.具体代码实现1.类模板的创建2.构造函数1.无参构造2.拷贝构造 迭代器构造和给定n个val值构造以及析构函数3.空间扩容1.reserve2.resize4.操作符重载1.[ ]重载2.赋值运算符重载5.数据增加和删除1.尾插2.任意位置插入3.任意位置删除4.尾删6.一些其他接口3.总结前言
本文主要对vector容器的实现进行讲解vector我们在使用的感觉它有点像数组它也是个类模板可以根据需要实例化出不同的模板类用于存储数据。它的底层实现也是像之前实现的顺序表。本文主要参考库中的vector实现通过模拟实现让我们对容器理解更加深刻。 1.大体思路 这个vector容器底层也和顺序表类似在实现的时候我们可以先去看看库中源码。这里就不放出库中源码截图了。直接说结论吧库中的vector类模板主要有以下几个成员:_start _finish _end_of_storage这个3个成员变量有之前实现顺序表的基础相信很容易看出来_start肯定是指向存储数据首地址的finish是存储末尾数据位置的后一个位置end是指向存储数据的空间最后一个位置也就是相当于capacity。这个3个成员变量是指针类型这是为了后续实现迭代器比较方便于才这样设计的。大概了解成员变量的组成后就可以着手实现了。这里我们也仿照库中实现按照类模板的方式去实现。 2.具体代码实现
1.类模板的创建
namespace Ly
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};
}这里我们也用命名空间的方式将其封起来避免和库中vector起冲突。这里的vector底层存储数据的那一套和顺序表类似可以天然的使用原生指针作为迭代器。这里为了图方便就不走初始化列表了直接给缺省值。 2.构造函数 构函数这里有很多细节需要注意有些地方需要复用其他成员函数。这里为了理清逻辑我们先画图分析一下。 具体问题如下图以string为例 在实现vector的时候会涉及到更深层次的拷贝的相当于要做两次深拷贝处理这点需要我们注意 1.无参构造
vector()
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}这里的无参构造很简单不过多的赘述了。我们主要看看下面的几种构造。 2.拷贝构造 迭代器构造和给定n个val值构造以及析构函数
vector(size_t n,const T val){reserve(n);for (int i 0; i n; i){push_back(val);}}这里直接复用reserve进行扩容然后复用尾插插入数据这两个接口下面会介绍具体实现的这里先不着急。 vector(const vectorT val){_start new T[val.capacity()];for (size_t i 0; i val.size(); i){_start[i] val._start[i];}_finish _start val.size();_end_of_storage _start val.capacity();/*_start new T[val.capacity()];memcpy(_start, val._start, sizeof(T)*val.size());_finish _start val.size();_end_of_storage _start val.capacity();*/}这个拷贝构造我们采用赋值形式的进行数据的拷贝如果是自定义类型这个赋值会调用后续实现的operator函数如果不是自定义类型就是直接赋值和memcpy一样的处理方式这样就不会出现问题了。这个_finish和_end_of_storage记得及时更新。至于为啥采用赋值的形式我上面说的很清楚了这里就不在赘述了。还有需要注意的类名T才是类型这点在之前的模板博客中提到过。 // 重新声明迭代器迭代器区间[first,last)可以是任意容器的迭代器templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}这里迭代器构造的时候需要在定义一个模板参数这样这个迭代器构造函数可以传任意容器的迭代器作为参数进行构造。 补充一个构造
//避免模板示例化的时候误调上面的迭代器构造vector(int n, const T val){reserve(n);for (int i 0; i n; i){push_back(val);}}理论上将提供了vector(size_t n, const T value T())之后vector(int n, const T value T())就不需要提供了但是对于 vector v(2, 1); 编译器在编译时认为T已经被实例化为int而2和1编译器会默认其为int类型 就不会走vector(size_t n, const T value T())这个构造方法 最终选择vector(InputIterator first, InputIterator last)因为编译器觉得区间构造两个参数类型一致因此编译器就会将InputIterator实例化为int但是10和5根本不是一个区间编译时就报错了故需要增加该构造方法 ~vector(){delete[] _start;_start _finish _end_of_storage nullptr;}这里析构函数也很简单释放空间后直接置空。 3.空间扩容
1.reserve
void reserve(size_t n){ //需要提前之前的size的大小保存起来确定_finsh的位置size_t sz size();if (n capacity()){T* tem new T[n];if (_start){for (size_t i 0; i val.size(); i){_start[i] val._start[i];}delete[] _start;}_start tem;_end_of_storage tem n;_finish temsz;}}只有当n大于capccity的时候才会进行扩容处理其中扩容的时候会涉及到数据的拷贝所以我们这里还是采用赋值的形式来处理之前实现的时候是采用memcpy进行直接拷贝上面说了这种拷贝处理是有问题的所以采用赋值的形式。这里要加上一个判断_start为空的时候调用resreve实际上是构造函数调用它进行扩容这个时候reserve只是单独的扩容而已。还有一点需要注意之前的sz需要保存起来。这为啥需要保存起来呢我们知道这3个成员变量都是指针如何确定3个指针的指向呢_start很容易确定剩下的两个都可以通过_start来确定_startsize_finish_startcapacityend_of_storage,然而我们的size和capacity都是通过上述两个成员变量和_start相减来确定的。假如我们先更新了_start,那么_finish_startsize 然而size_finish -_start等价代换之后_finish_start_finsh-_start_finish相当于_finish没有更新。所以我们需要提前保存sz。 2.resize
void resize(int n, const T valT()){ //相当于删除数据if (n size()){_finish _start n;}else{if (n capacity()){reserve(n);}while (_finish ! _end_of_storage){*_finish val;_finish;}}}这里有一些细节需要注意。关于这个n的3种分类情况我就不多说了和string类似处理。我们看到形参是给了缺省值的我们知道对于内置类型来说是没有构造函数这么一说的那如果T实例化成内置类型怎么办呢C中为了配合模板的使用内置类型也是有构造函数的但是只是限于在使用模板的时候还有一点我们看到给的缺省值是个匿名对象我们知道匿名对象的使用周期很短只有一行这里为啥还是使用呢被const加修饰的匿名对象生命周期会被延长需要注意的是匿名对象具有常性如果不加const会报错。 4.操作符重载 操作符重载我们的重点放在赋值运算符重载上这是后续很多地方都需要用到的。 1.[ ]重载
T operator[](size_t pos){assert(pos size());return _start[pos];}[ ]重载支持下标访问这点就不多说了和string类似的处理。 2.赋值运算符重载
//这个是引用作为参数void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._end_of_storage);}//这个是传值传参 不影响实参vectorT operator(vectorT v){swap(v);return *this;}我看到这个赋值重载是传值传参不是传引用传参所以不会影响实参这个形参是临时变量但是这个临时变量会调用拷贝构造所以这个临时变量的存储数据的空间也是独立的我们在调用swap和这个临时变量进行交换即可这样就完成了一次赋值操作。交换后实际上影响的是这个临时变量这样处理极为巧妙。这里的细节主要在这个swap函数和这个重载函数的形参的传递形式上。 5.数据增加和删除
1.尾插
void push_back(const T val){if (size() capacity()){reserve(capacity()0?4:2* capacity());}*_finish val;_finish;}这里尾插的时候需要注意一下如果capacity为0这个时候需要将它修正为不为0的数这样才会正常的扩容。如果原有的空间满了我们按照二倍的方式进行扩容。 2.任意位置插入
iterator insert(iterator pos, const T val){ assert(pos _start pos _finish);if (_finish _end_of_storage){ //防止扩容之后迭代器失效int len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());pos _start len;}iterator end _finish;while (endpos){*end *(end - 1);end--;}*pos val;_finish;return pos;}这里有个特别重要的点就是迭代器失效问题这是为啥呢我们在进行插入的时候会进行扩容扩容之后这个pos就会变成野指针扩容的时候原有的空间被释放了重新申请的空间,为了避免这种情况我们提前记录好pos和_start之间的间距。剩下的就是挪动数据了这个挪动数据不用像之前string那样考虑什么无符号整形减的时候会数值会变大。但是注意我们在外部调用这个插入接口的时候外部的迭代器可能会失效买这个时候需要更新重新接收插入之后的pos值返回值我们也设置为迭代器类型便于接收新的pos位置。 3.任意位置删除
iterator erase(iterator pos){assert(pos _start pos _finish);iterator start pos 1;while (start!_finish){*(start - 1) *start;start;}--_finish;return pos;}迭代器都是常用来判断遍历的这里我们也按照这样的方式遍历。我们考虑一个问题删除的时候迭代器会失效吗从代码上看删除数据不需要扩容貌似迭代器不会失效我们来看看如下的情况 从图我们看出删除的时候也会造成迭代器失效如果这个图中的it在去访问就是非法操作。vs中对于这点处理的比较严格直接会断言报错Liunx下有相对宽松一点程序有时候不会报错。 4.尾删
void pop_back(){assert(!empty());--_finish;}这里尾插就更简单了_finish–即可注意删除的时候vector不能为空 6.一些其他接口 iterator begin(){return _start;}iterator end(){return _finish;}这里迭代器实现就比较简单了vector的迭代器可以直接用原生指针来实现。这里const的迭代器没有写这个实现就是把iterator换成const_iterator即可也很简单 size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_storage- _start;}bool empty()const{return _start _finish;}上面这些接口很简单没啥好说的看代码就能懂。 3.总结 关于这个vetcor实现其中最值得注意的几个点是1.拷贝构造的时候可能涉及到更深层次的拷贝我们这里不采用memcpy的方式处理memcpy处理内置类型没啥问题如果是自定义类型就会出现问题我们采用赋值的方式进行数据的拷贝这样对于自定义类型来说会调用拷贝构造对于内置类型处理方式和memcpy是一样的因为我们别的构造函数调用了这个尾插使所以尾插也是使用的直接赋值的形式。2.第二点就是这个赋值重载的时候调用swap这个形参的使用是个细节需要注意。3.第三点就是迭代器在使用的可能会造成迭代器失效的问题这点需要考虑清楚不然会有很严重的问题。所以我们在使用迭代器的时候一定要注意及时更新迭代器。 以上内容如有问题欢迎指正
